#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

//堆排序
/*堆排序的步骤
 * 首先把堆调整为大根堆，然后根部元素str[0]
 *和最后一个元素进行交换，这样最大的元素就放到了数组最后，
 * 接着将剩余的9个元素继续调整为大根堆，然后交换str[0]和9
 *个元素中的最后一个，循环往复，直到有序
 * */
typedef int ElemType;
typedef struct SSTable {
    ElemType lenth;
    ElemType *str;
} SSTable;

void SST_Init(SSTable &T, int len) {
    T.lenth = len;
    T.str = (ElemType *) malloc(sizeof(ElemType) * T.lenth);
//    int a[10]={3,87,2,93,78,56,61,38,12,40};
//    memcpy(T.str,a,sizeof(a));
    srand(time(NULL));
    for (int i = 0; i < T.lenth; i++) {
        T.str[i] = rand() % 100;
    }
}

void array_print(SSTable T) {
    for (int i = 0; i < T.lenth; i++) {
        printf("%3d", T.str[i]);
    }
    printf("\n");
}
void array_print_str(ElemType *str,int len) {
    for (int i = 0; i < len; i++) {
        printf("%3d", str[i]);
    }
    printf("\n");
}

void swap(int &a, int &b) {
    a ^= b;
    b ^= a;
    a ^= b;
}

//把某个子树调整为大根堆
void AjustDown(ElemType *str, int k, ElemType len) {
    int dad = k;//父亲的下标
    int son = 2 * dad + 1;//左孩子的下标
    while (son < len) {
        if (son + 1 < len && str[son] < str[son + 1]) {//如果左孩子小于右孩子
            //比较左孩子和右孩子的大小，若左孩子小于右孩子进入if语句
            //左孩子大于右孩子则无需进入if语句
            son++;//拿右孩子和父亲比
        }
        if (str[son] > str[dad]) {//如果孩子结点大于父结点，则交换两个的值
            swap(str[son], str[dad]);//交换
            //son重新作为dad，去判断剩下的子树是否符合大根堆
            dad = son;
            son = 2 * dad + 1;
        } else {
            break;
        }
    }
}

void HeapSort(ElemType *str, ElemType len) {
    //将堆调整为大根堆
    int i;
    //先调最后一棵子树
    for (i = len / 2 - 1; i >= 0; i--) {
        AjustDown(str, i, len);
    }
    swap(str[0], str[len - 1]);//交换根部元素和最后一个元素
    for (i = len - 1; i > 1; i--) {//i代表的是剩余的无序数的数组的长度
        AjustDown(str, 0, i);//调整剩余元素为大根堆
        swap(str[0], str[i - 1]);//交换根部元素和无序数的数组的最后一个元素
    }
}

int main() {
    SSTable T;
    SST_Init(T, 10);
    array_print(T);
    HeapSort(T.str, T.lenth);//所有元素参与排序
    array_print(T);
    return 0;
}
